import unittest
from typing import List


class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        ret = 0
        nums.sort()
        for idx, num in enumerate(nums[0: len(nums) - 1]):
            idx_min = self.binary_search_ge(nums, lower - num)
            if idx_min <= idx:
                idx_min = idx + 1
            idx_max = self.binary_search_ge(nums, upper - num + 1)
            if idx_max <= idx:
                continue
            ret += idx_max - idx_min
        return ret

    def binary_search_ge(self, arr: List[int], target):
        left = -1
        right = len(arr)
        while left + 1 < right:
            mid = (left + right) // 2
            if arr[mid] >= target:
                right = mid
            else:
                left = mid
        return right

class Test(unittest.TestCase):
    def test_case_1(self):
        ret = Solution().countFairPairs([0, 1, 7, 4, 4, 5], 3, 6)
        self.assertEqual(6, ret)
